package com.zhugang.week12;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: findClosest
 * @author: chanzhugang
 * @create: 2022/09/07 15:27
 */
public class FindClosest {

    /**
     * 面试题 17.11 单词距离
     *
     * @param words
     * @param word1
     * @param word2
     * @return
     */
    public int findClosest(String[] words, String word1, String word2) {
        // 两个单词最短距离
        // 把两个单词在数组中的位置记录下来，利用双指针求解，类似求最小差问题（合并两个有序数组）
        // 把新题目转化为做过的题目
        List<Integer> w1List = new ArrayList<>();
        List<Integer> w2List = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word.equals(word1)) {
                w1List.add(i);
            }
            if (word.equals(word2)) {
                w2List.add(i);
            }
        }

        // 求最小差值
        int i = 0;
        int j = 0;
        int minResult = Integer.MAX_VALUE;
        while (i < w1List.size() && j < w2List.size()) {
            int posi = w1List.get(i);
            int posj = w2List.get(j);
            if (posi > posj) {
                minResult = Math.min(minResult, posi - posj);
                j++;
            } else {
                minResult = Math.min(minResult, posj - posi);
                i++;
            }
        }
        return minResult;
    }
}